Field
The following relates to methods and apparatus for use in the design and manufacture of integrated circuits, and particularly to the design and manufacture of circuits that perform divisions.
Related Art
When designing and manufacturing ICs, sophisticated synthesis tools such as Synopsis™ Design Compiler are used to convert a desired function which must be implemented in the IC into a set of logic gates to perform the functions. Functions which need to be implemented include add, subtract, multiply and divide. The synthesis tools seek to implement the desired functions in an efficient manner in logic gates.
The tools operate by converting a function to be implemented, such as divide by x, to what is known as register transfer level (RTL), which defines a circuit's behavior in terms of the flow of signals between hardware registers and the logical operations performed on these signals. This is then used to generate a high level representation of a circuit from which appropriate gate level representations and the ultimate IC design can be derived for manufacture, and an IC can then be made. If a synthesis tool is presented with division by a constant such as x/d, it will invariably use RTL designed for non-constant division. A designer could note that in the case of constant division an implementation of the form (ax+b)/2k could potentially make smaller ICs. The designer would then have to work out values for the triple (a,b,k) which would perform the task of x/d. As explained in the Summary below, the present inventors have appreciated that by representing integer division in the form (ax+b)/2k rather than the conventional x/d division input to an RTL generator, the division is implemented using a multiply-add implementation for various rounding modes.
Division is acknowledged to be an expensive operation to perform in hardware. However in the case where the divisor is known to be a constant, efficient hardware implementations can be constructed. Consider the division of an unsigned n bit integer x by a known invariant integer constant d:
            x      d        ⁢    x    ∈            [              0        ,                              2            n                    -          1                    ]        ⁢    d    ∈  N
For the purposes of the exposition we will assume that d is an odd integer larger than 1, the following schemes can be easily modified for even d by those skilled in the art. We consider an implementation of the form:
      x    d    ≈      ⌊                  ax        +        b                    2        k              ⌋  
Where a, b and k are non negative integers. Note that without loss of generality we can assume that a is odd. The prior art in the case where the rounding used is round towards zero and d is an unsigned m bit number comes from [1] and can be succinctly summarised setting:
            ⌊              x        d            ⌋        =          ⌊                        ax          +          b                          2          k                    ⌋            t    =          ⌊                        2                      n            +            m            -            1                          d            ⌋            k    =          n      +      m      -      1                                    a          =                                    (                                                                    d                    ⁡                                          (                                              t                        +                        1                                            )                                                        ⁢                  mod                  ⁢                                                                          ⁢                                      2                    n                                                  ≤                                  2                                      m                    -                    1                                                              )                        ?                                                            t            +            1                    :          t                                              b          =                                    (                                                                    d                    ⁡                                          (                                              t                        +                        1                                            )                                                        ⁢                  mod                  ⁢                                                                          ⁢                                      2                    n                                                  ≤                                  2                                      m                    -                    1                                                              )                        ?                                                0          :          t                    
The second piece of prior art comes from [2] where the rounding mode used is round to nearest, d=2n−1 and x is the result of a multiplication of two unsigned n bit numbers a and b:
      ⌊                  ab                              2            n                    -          1                    +              1        2              ⌋    =      ⌊                            (                                    2              n                        +            1                    )                ⁢                  (                      ab            +                          2                              n                -                1                                              )                            2                  2          ⁢          n                      ⌋  
When a division is to be performed such as divide by d, the integer triple discussed above is generated and provided to a RTL generation unit, which produces the gate level circuits required as an input to a synthesis tool which then generates the hardware components required for manufacture.